home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 21 / AACD 21.iso / AACD / Utilities / Ghostscript / src / ilocate.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-01  |  13.7 KB  |  510 lines
  1. /* Copyright (C) 1995, 1996, 1997, 1998, 1999, 2000 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of AFPL Ghostscript.
  4.   
  5.   AFPL Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author or
  6.   distributor accepts any responsibility for the consequences of using it, or
  7.   for whether it serves any particular purpose or works at all, unless he or
  8.   she says so in writing.  Refer to the Aladdin Free Public License (the
  9.   "License") for full details.
  10.   
  11.   Every copy of AFPL Ghostscript must include a copy of the License, normally
  12.   in a plain ASCII text file named PUBLIC.  The License grants you the right
  13.   to copy, modify and redistribute AFPL Ghostscript, but only under certain
  14.   conditions described in the License.  Among other things, the License
  15.   requires that the copyright notice and this notice be preserved on all
  16.   copies.
  17. */
  18.  
  19. /*$Id: ilocate.c,v 1.3 2000/09/19 19:00:44 lpd Exp $ */
  20. /* Object locating and validating for Ghostscript memory manager */
  21. #include "ghost.h"
  22. #include "memory_.h"
  23. #include "errors.h"
  24. #include "gsexit.h"
  25. #include "gsstruct.h"
  26. #include "iastate.h"
  27. #include "idict.h"
  28. #include "igc.h"        /* for gc_state_t */
  29. #include "igcstr.h"        /* for prototype */
  30. #include "iname.h"
  31. #include "ipacked.h"
  32. #include "isstate.h"
  33. #include "iutil.h"        /* for packed_get */
  34. #include "ivmspace.h"
  35. #include "store.h"
  36.  
  37. /* ================ Locating ================ */
  38.  
  39. /* Locate a pointer in the chunks of a space being collected. */
  40. /* This is only used for string garbage collection and for debugging. */
  41. chunk_t *
  42. gc_locate(const void *ptr, gc_state_t * gcst)
  43. {
  44.     const gs_ref_memory_t *mem;
  45.     const gs_ref_memory_t *other;
  46.  
  47.     if (chunk_locate(ptr, &gcst->loc))
  48.     return gcst->loc.cp;
  49.     mem = gcst->loc.memory;
  50.  
  51.     /*
  52.      * Try the stable allocator of this space, or, if the current memory
  53.      * is the stable one, the non-stable allocator of this space.
  54.      */
  55.  
  56.     if ((other = (const gs_ref_memory_t *)mem->stable_memory) != mem ||
  57.     (other = gcst->spaces_indexed[mem->space >> r_space_shift]) != mem
  58.     ) {
  59.     gcst->loc.memory = other;
  60.     gcst->loc.cp = 0;
  61.     if (chunk_locate(ptr, &gcst->loc))
  62.         return gcst->loc.cp;
  63.     }
  64.  
  65.     /*
  66.      * Try the other space, if there is one, including its stable allocator
  67.      * and all save levels.  (If the original space is system space, try
  68.      * local space.)
  69.      */
  70.  
  71.     if (gcst->space_local != gcst->space_global) {
  72.     gcst->loc.memory = other =
  73.         (mem->space == avm_local ? gcst->space_global : gcst->space_local);
  74.     gcst->loc.cp = 0;
  75.     if (chunk_locate(ptr, &gcst->loc))
  76.         return gcst->loc.cp;
  77.     /* Try its stable allocator. */
  78.     if (other->stable_memory != (const gs_memory_t *)other) {
  79.         gcst->loc.memory = (gs_ref_memory_t *)other->stable_memory;
  80.         gcst->loc.cp = 0;
  81.         if (chunk_locate(ptr, &gcst->loc))
  82.         return gcst->loc.cp;
  83.         gcst->loc.memory = other;
  84.     }
  85.     /* Try other save levels of this space. */
  86.     while (gcst->loc.memory->saved != 0) {
  87.         gcst->loc.memory = &gcst->loc.memory->saved->state;
  88.         gcst->loc.cp = 0;
  89.         if (chunk_locate(ptr, &gcst->loc))
  90.         return gcst->loc.cp;
  91.     }
  92.     }
  93.  
  94.     /*
  95.      * Try system space.  This is simpler because it isn't subject to
  96.      * save/restore and doesn't have a separate stable allocator.
  97.      */
  98.  
  99.     if (mem != gcst->space_system) {
  100.     gcst->loc.memory = gcst->space_system;
  101.     gcst->loc.cp = 0;
  102.     if (chunk_locate(ptr, &gcst->loc))
  103.         return gcst->loc.cp;
  104.     }
  105.  
  106.     /*
  107.      * Try other save levels of the initial space, or of global space if the
  108.      * original space was system space.  In the latter case, try all
  109.      * levels, and its stable allocator.
  110.      */
  111.  
  112.     switch (mem->space) {
  113.     default:            /* system */
  114.     other = gcst->space_global;
  115.     if (other->stable_memory != (const gs_memory_t *)other) {
  116.         gcst->loc.memory = (gs_ref_memory_t *)other->stable_memory;
  117.         gcst->loc.cp = 0;
  118.         if (chunk_locate(ptr, &gcst->loc))
  119.         return gcst->loc.cp;
  120.     }
  121.     gcst->loc.memory = other;
  122.     break;
  123.     case avm_global:
  124.     gcst->loc.memory = gcst->space_global;
  125.     break;
  126.     case avm_local:
  127.     gcst->loc.memory = gcst->space_local;
  128.     break;
  129.     }
  130.     for (;;) {
  131.     if (gcst->loc.memory != mem) {    /* don't do twice */
  132.         gcst->loc.cp = 0;
  133.         if (chunk_locate(ptr, &gcst->loc))
  134.         return gcst->loc.cp;
  135.     }
  136.     if (gcst->loc.memory->saved == 0)
  137.         break;
  138.     gcst->loc.memory = &gcst->loc.memory->saved->state;
  139.     }
  140.  
  141.     /* Restore locator to a legal state and report failure. */
  142.  
  143.     gcst->loc.memory = mem;
  144.     gcst->loc.cp = 0;
  145.     return 0;
  146. }
  147.  
  148. /* ================ Debugging ================ */
  149.  
  150. #ifdef DEBUG
  151.  
  152. /* Define the structure for temporarily saving allocator state. */
  153. typedef struct alloc_temp_save_s {
  154.     chunk_t cc;
  155.     uint rsize;
  156.     ref rlast;
  157. } alloc_temp_save_t;
  158. /* Temporarily save the state of an allocator. */
  159. private void
  160. alloc_temp_save(alloc_temp_save_t *pats, gs_ref_memory_t *mem)
  161. {
  162.     chunk_t *pcc = mem->pcc;
  163.     obj_header_t *rcur = mem->cc.rcur;
  164.  
  165.     if (pcc != 0) {
  166.     pats->cc = *pcc;
  167.     *pcc = mem->cc;
  168.     }
  169.     if (rcur != 0) {
  170.     pats->rsize = rcur[-1].o_size;
  171.     rcur[-1].o_size = mem->cc.rtop - (byte *) rcur;
  172.     /* Create the final ref, reserved for the GC. */
  173.     pats->rlast = ((ref *) mem->cc.rtop)[-1];
  174.     make_mark((ref *) mem->cc.rtop - 1);
  175.     }
  176. }
  177. /* Restore the temporarily saved state. */
  178. private void
  179. alloc_temp_restore(alloc_temp_save_t *pats, gs_ref_memory_t *mem)
  180. {
  181.     chunk_t *pcc = mem->pcc;
  182.     obj_header_t *rcur = mem->cc.rcur;
  183.  
  184.     if (rcur != 0) {
  185.     rcur[-1].o_size = pats->rsize;
  186.     ((ref *) mem->cc.rtop)[-1] = pats->rlast;
  187.     }
  188.     if (pcc != 0)
  189.     *pcc = pats->cc;
  190. }
  191.  
  192. /* Validate the contents of an allocator. */
  193. void
  194. ialloc_validate_spaces(const gs_dual_memory_t * dmem)
  195. {
  196.     int i;
  197.     gc_state_t state;
  198.     alloc_temp_save_t
  199.     save[countof(dmem->spaces_indexed)],
  200.     save_stable[countof(dmem->spaces_indexed)];
  201.     gs_ref_memory_t *mem;
  202.  
  203.     state.spaces = dmem->spaces;
  204.     state.loc.memory = state.space_local;
  205.     state.loc.cp = 0;
  206.  
  207.     /* Save everything we need to reset temporarily. */
  208.  
  209.     for (i = 0; i < countof(save); i++)
  210.     if ((mem = dmem->spaces_indexed[i]) != 0) {
  211.         alloc_temp_save(&save[i], mem);
  212.         if (mem->stable_memory != (gs_memory_t *)mem)
  213.         alloc_temp_save(&save_stable[i],
  214.                 (gs_ref_memory_t *)mem->stable_memory);
  215.     }
  216.  
  217.     /* Validate memory. */
  218.  
  219.     for (i = 0; i < countof(save); i++)
  220.     if ((mem = dmem->spaces_indexed[i]) != 0) {
  221.         ialloc_validate_memory(mem, &state);
  222.         if (mem->stable_memory != (gs_memory_t *)mem)
  223.         ialloc_validate_memory((gs_ref_memory_t *)mem->stable_memory,
  224.                        &state);
  225.     }
  226.  
  227.     /* Undo temporary changes. */
  228.  
  229.     for (i = 0; i < countof(save); i++)
  230.     if ((mem = dmem->spaces_indexed[i]) != 0) {
  231.         if (mem->stable_memory != (gs_memory_t *)mem)
  232.         alloc_temp_restore(&save_stable[i],
  233.                    (gs_ref_memory_t *)mem->stable_memory);
  234.         alloc_temp_restore(&save[i], mem);
  235.     }
  236. }
  237. void
  238. ialloc_validate_memory(const gs_ref_memory_t * mem, gc_state_t * gcst)
  239. {
  240.     const gs_ref_memory_t *smem;
  241.     int level;
  242.  
  243.     for (smem = mem, level = 0; smem != 0;
  244.      smem = &smem->saved->state, --level
  245.     ) {
  246.     const chunk_t *cp;
  247.     int i;
  248.  
  249.     if_debug3('6', "[6]validating memory 0x%lx, space %d, level %d\n",
  250.           (ulong) mem, mem->space, level);
  251.     /* Validate chunks. */
  252.     for (cp = smem->cfirst; cp != 0; cp = cp->cnext)
  253.         ialloc_validate_chunk(cp, gcst);
  254.     /* Validate freelists. */
  255.     for (i = 0; i < num_freelists; ++i) {
  256.         uint free_size = i << log2_obj_align_mod;
  257.         const obj_header_t *pfree;
  258.  
  259.         for (pfree = mem->freelists[i]; pfree != 0;
  260.          pfree = *(const obj_header_t * const *)pfree
  261.         ) {
  262.         uint size = pfree[-1].o_size;
  263.  
  264.         if (pfree[-1].o_type != &st_free) {
  265.             lprintf3("Non-free object 0x%lx(%u) on freelist %i!\n",
  266.                  (ulong) pfree, size, i);
  267.             break;
  268.         }
  269.         if ((i == LARGE_FREELIST_INDEX && size < max_freelist_size) ||
  270.          (i != LARGE_FREELIST_INDEX && 
  271.          (size < free_size - obj_align_mask || size > free_size))) {
  272.             lprintf3("Object 0x%lx(%u) size wrong on freelist %i!\n",
  273.                  (ulong) pfree, size, i);
  274.             break;
  275.         }
  276.         }
  277.     }
  278.     };
  279. }
  280.  
  281. /* Check the validity of an object's size. */
  282. inline private bool
  283. object_size_valid(const obj_header_t * pre, uint size, const chunk_t * cp)
  284. {
  285.     return (pre->o_alone ? (const byte *)pre == cp->cbase :
  286.         size <= cp->ctop - (const byte *)(pre + 1));
  287. }
  288.  
  289. /* Validate all the objects in a chunk. */
  290. private void ialloc_validate_ref(P2(const ref *, gc_state_t *));
  291. private void ialloc_validate_ref_packed(P2(const ref_packed *, gc_state_t *));
  292. void
  293. ialloc_validate_chunk(const chunk_t * cp, gc_state_t * gcst)
  294. {
  295.     if_debug_chunk('6', "[6]validating chunk", cp);
  296.     SCAN_CHUNK_OBJECTS(cp);
  297.     DO_ALL
  298.     if (pre->o_type == &st_free) {
  299.         if (!object_size_valid(pre, size, cp))
  300.         lprintf3("Bad free object 0x%lx(%lu), in chunk 0x%lx!\n",
  301.              (ulong) (pre + 1), (ulong) size, (ulong) cp);
  302.     } else
  303.         ialloc_validate_object(pre + 1, cp, gcst);
  304.     if_debug3('7', " [7]validating %s(%lu) 0x%lx\n",
  305.           struct_type_name_string(pre->o_type),
  306.           (ulong) size, (ulong) pre);
  307.     if (pre->o_type == &st_refs) {
  308.     const ref_packed *rp = (const ref_packed *)(pre + 1);
  309.     const char *end = (const char *)rp + size;
  310.  
  311.     while ((const char *)rp < end) {
  312.         ialloc_validate_ref_packed(rp, gcst);
  313.         rp = packed_next(rp);
  314.     }
  315.     } else {
  316.     struct_proc_enum_ptrs((*proc)) = pre->o_type->enum_ptrs;
  317.     uint index = 0;
  318.     enum_ptr_t eptr;
  319.     gs_ptr_type_t ptype;
  320.  
  321.     if (proc != gs_no_struct_enum_ptrs)
  322.         for (; (ptype = (*proc) (pre + 1, size, index, &eptr, pre->o_type, NULL)) != 0; ++index)
  323.         if (eptr.ptr == 0)
  324.             DO_NOTHING;
  325.         else if (ptype == ptr_struct_type)
  326.             ialloc_validate_object(eptr.ptr, NULL, gcst);
  327.         else if (ptype == ptr_ref_type)
  328.             ialloc_validate_ref_packed(eptr.ptr, gcst);
  329.     }
  330.     END_OBJECTS_SCAN
  331. }
  332. /* Validate a ref. */
  333. private void
  334. ialloc_validate_ref_packed(const ref_packed * rp, gc_state_t * gcst)
  335. {
  336.     if (r_is_packed(rp)) {
  337.     ref unpacked;
  338.  
  339.     packed_get(rp, &unpacked);
  340.     ialloc_validate_ref(&unpacked, gcst);
  341.     } else {
  342.     ialloc_validate_ref((const ref *)rp, gcst);
  343.     }
  344. }
  345. private void
  346. ialloc_validate_ref(const ref * pref, gc_state_t * gcst)
  347. {
  348.     const void *optr;
  349.     const ref *rptr;
  350.     const char *tname;
  351.     uint size;
  352.  
  353.     if (!gs_debug_c('?'))
  354.     return;            /* no check */
  355.     if (r_space(pref) == avm_foreign)
  356.     return;
  357.     switch (r_type(pref)) {
  358.     case t_file:
  359.         optr = pref->value.pfile;
  360.         goto cks;
  361.     case t_device:
  362.         optr = pref->value.pdevice;
  363.         goto cks;
  364.     case t_fontID:
  365.     case t_struct:
  366.     case t_astruct:
  367.         optr = pref->value.pstruct;
  368. cks:        if (optr != 0)
  369.         ialloc_validate_object(optr, NULL, gcst);
  370.         break;
  371.     case t_name:
  372.         if (name_index_ptr(name_index(pref)) != pref->value.pname) {
  373.         lprintf3("At 0x%lx, bad name %u, pname = 0x%lx\n",
  374.              (ulong) pref, (uint)name_index(pref),
  375.              (ulong) pref->value.pname);
  376.         break;
  377.         } {
  378.         ref sref;
  379.  
  380.         name_string_ref(pref, &sref);
  381.         if (r_space(&sref) != avm_foreign &&
  382.             !gc_locate(sref.value.const_bytes, gcst)
  383.             ) {
  384.             lprintf4("At 0x%lx, bad name %u, pname = 0x%lx, string 0x%lx not in any chunk\n",
  385.                  (ulong) pref, (uint) r_size(pref),
  386.                  (ulong) pref->value.pname,
  387.                  (ulong) sref.value.const_bytes);
  388.         }
  389.         }
  390.         break;
  391.     case t_string:
  392.         if (r_size(pref) != 0 && !gc_locate(pref->value.bytes, gcst))
  393.         lprintf3("At 0x%lx, string ptr 0x%lx[%u] not in any chunk\n",
  394.              (ulong) pref, (ulong) pref->value.bytes,
  395.              (uint) r_size(pref));
  396.         break;
  397.     case t_array:
  398.         if (r_size(pref) == 0)
  399.         break;
  400.         rptr = pref->value.refs;
  401.         size = r_size(pref);
  402.         tname = "array";
  403. cka:        if (!gc_locate(rptr, gcst)) {
  404.         lprintf3("At 0x%lx, %s 0x%lx not in any chunk\n",
  405.              (ulong) pref, tname, (ulong) rptr);
  406.         break;
  407.         } {
  408.         uint i;
  409.  
  410.         for (i = 0; i < size; ++i) {
  411.             const ref *elt = rptr + i;
  412.  
  413.             if (r_is_packed(elt))
  414.             lprintf5("At 0x%lx, %s 0x%lx[%u] element %u is not a ref\n",
  415.                  (ulong) pref, tname, (ulong) rptr, size, i);
  416.         }
  417.         }
  418.         break;
  419.     case t_shortarray:
  420.     case t_mixedarray:
  421.         if (r_size(pref) == 0)
  422.         break;
  423.         optr = pref->value.packed;
  424.         if (!gc_locate(optr, gcst))
  425.         lprintf2("At 0x%lx, packed array 0x%lx not in any chunk\n",
  426.              (ulong) pref, (ulong) optr);
  427.         break;
  428.     case t_dictionary:
  429.         {
  430.         const dict *pdict = pref->value.pdict;
  431.  
  432.         if (!r_has_type(&pdict->values, t_array) ||
  433.             !r_is_array(&pdict->keys) ||
  434.             !r_has_type(&pdict->count, t_integer) ||
  435.             !r_has_type(&pdict->maxlength, t_integer)
  436.             )
  437.             lprintf2("At 0x%lx, invalid dict 0x%lx\n",
  438.                  (ulong) pref, (ulong) pdict);
  439.         rptr = (const ref *)pdict;
  440.         }
  441.         size = sizeof(dict) / sizeof(ref);
  442.         tname = "dict";
  443.         goto cka;
  444.     }
  445. }
  446.  
  447. /* Validate an object. */
  448. void
  449. ialloc_validate_object(const obj_header_t * ptr, const chunk_t * cp,
  450.                gc_state_t * gcst)
  451. {
  452.     const obj_header_t *pre = ptr - 1;
  453.     ulong size = pre_obj_contents_size(pre);
  454.     gs_memory_type_ptr_t otype = pre->o_type;
  455.     const char *oname;
  456.  
  457.     if (!gs_debug_c('?'))
  458.     return;            /* no check */
  459.     if (cp == 0 && gcst != 0) {
  460.     gc_state_t st;
  461.  
  462.     st = *gcst;        /* no side effects! */
  463.     if (!(cp = gc_locate(pre, &st))) {
  464.         lprintf1("Object 0x%lx not in any chunk!\n",
  465.              (ulong) ptr);
  466.         return;        /*gs_abort(); */
  467.     }
  468.     }
  469.     if (otype == &st_free) {
  470.     lprintf3("Reference to free object 0x%lx(%lu), in chunk 0x%lx!\n",
  471.          (ulong) ptr, (ulong) size, (ulong) cp);
  472.     gs_abort();
  473.     }
  474.     if ((cp != 0 && !object_size_valid(pre, size, cp)) ||
  475.     otype->ssize == 0 ||
  476.     size % otype->ssize != 0 ||
  477.     (oname = struct_type_name_string(otype),
  478.      *oname < 33 || *oname > 126)
  479.     ) {
  480.     lprintf4("Bad object 0x%lx(%lu), ssize = %u, in chunk 0x%lx!\n",
  481.          (ulong) ptr, (ulong) size, otype->ssize, (ulong) cp);
  482.     gs_abort();
  483.     }
  484. }
  485.  
  486. #else /* !DEBUG */
  487.  
  488. void
  489. ialloc_validate_spaces(const gs_dual_memory_t * dmem)
  490. {
  491. }
  492.  
  493. void
  494. ialloc_validate_memory(const gs_ref_memory_t * mem, gc_state_t * gcst)
  495. {
  496. }
  497.  
  498. void
  499. ialloc_validate_chunk(const chunk_t * cp, gc_state_t * gcst)
  500. {
  501. }
  502.  
  503. void
  504. ialloc_validate_object(const obj_header_t * ptr, const chunk_t * cp,
  505.                gc_state_t * gcst)
  506. {
  507. }
  508.  
  509. #endif /* (!)DEBUG */
  510.